#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

class Graph {
private:
    int V; 
    vector<vector<int>> adj; 

public:
    Graph(int V) : V(V), adj(V) {}

    void add(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }

    void traverseDFS() {
        vector<bool> visited(V, false);
        for (int i = 0; i < V; ++i) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
        cout << endl;
    }

    void DFSUtil(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        for (int u : adj[v]) {
            if (!visited[u]) {
                DFSUtil(u, visited);
            }
        }
    }

    void traverseBFS() {
        vector<bool> visited(V, false);
        queue<int> q;

        for (int i = 0; i < V; ++i) {
            if (!visited[i]) {
                q.push(i);
                visited[i] = true;
                while (!q.empty()) {
                    int v = q.front();
                    q.pop();
                    cout << v << " ";
                    for (int u : adj[v]) {
                        if (!visited[u]) {
                            visited[u] = true;
                            q.push(u);
                        }
                    }
                }
            }
        }
        cout << endl;
    }
};

int main() {
    Graph g(5);
    g.add(0, 1);
    g.add(0, 2);
    g.add(1, 3);
    g.add(2, 3);
    g.add(4, 4); 

    cout << "DFS обход: ";
    g.traverseDFS();

    cout << "BFS обход: ";
    g.traverseBFS();

    return 0;
}
